#include <bits/stdc++.h>

using namespace std;

// 不含连续1的非负整数
// 给定一个正整数n，请你统计在[0, n]范围的非负整数中
// 有多少个整数的二进制表示中不存在连续的1
// 测试链接 : https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/

class Solution 
{
public:
    int findIntegers1(int n) 
    {
        int cnt[31];
        // 0 : ""
        // 1 : "0"、"1"
        // 2 : "00"、"01"、"10"
        cnt[0] = 1, cnt[1] = 2;
        for(int len = 2; len <= 30; ++len)
        {
            cnt[len] = cnt[len - 1] + cnt[len - 2];
        }
        return f(cnt, n, 30);
    }

	// cnt[len] : 二进制如果有len位，所有二进制状态中不存在连续的1的状态有多少个，辅助数组
	// 从num二进制形式的高位开始，当前来到第i位，之前的位完全和num一样
	// 返回<=num且不存在连续的1的状态有多少个
    int f(int* cnt, int num, int i)
    {
        if(i == -1) return 1; // num自身合法
        int ans = 0;
        if((num & (1 << i)) != 0)
        {
            ans += cnt[i]; // 第 i 位填 0
            if((num & (1 << (i + 1))) != 0)
            {
                // 如果num二进制状态，前一位是1，当前位也是1
				// 如果前缀保持和num一样，后续一定不合法了
				// 所以提前返回
                return ans;
            }
        }
        // 之前的高位和num一样，且合法，继续去i-1位递归
        ans += f(cnt, num, i - 1);
        return ans;
    }

	// 只是把方法1从递归改成迭代而已
	// 完全是等义改写，没有新东西
    int findIntegers2(int n) 
    {
        int cnt[31];
        // 0 : ""
        // 1 : "0"、"1"
        // 2 : "00"、"01"、"10"
        cnt[0] = 1, cnt[1] = 2;
        for(int len = 2; len <= 30; ++len)
        {
            cnt[len] = cnt[len - 1] + cnt[len - 2];
        }
        
        int ans = 0;
        for(int i = 30; i >= -1; --i)
        {
            if(i == -1)
            {
                ++ans;
                break;
            }
            if((n & (1 << i)) != 0)
            {
                ans += cnt[i];
                if((n & (1 << (i + 1))) != 0)
                {
                    break;
                }
            }
        }
        return ans;
    }
};


class Solution 
{
public:
    int findIntegers(int n) 
    {
        /*
        pre 表示第 i−1 位是否为 1，如果为真则当前位不能填 1。

        is_limit 表示当前是否受到了 n 的约束。若为真，则第 i 
        位填入的数字至多为 s[i]，否则可以是 1。如果在受到约束
        的情况下填了 s[i]，那么后续填入的数字仍会受到 n 的约束。

        is_num 表示 i 前面的数位是否填了数字。若为假，则当前位
        可以跳过（不填数字），或者要填入的数字至少为 1；若为真，
        则要填入的数字可以从 0 开始。

        对于本题来说，由于前导零对答案无影响，is_num 可以省略。
        */
        int m = __lg(n), dp[m + 1][2];
        memset(dp, -1, sizeof dp);
        function<int(int, bool, bool)> f = [&](int i, bool prev, bool is_limit)
        {
            if(i < 0) return 1;
            if(!is_limit && dp[i][prev] != -1) return dp[i][prev];
            int up = is_limit ? n >> i & 1 : 1;
            int ans = f(i - 1, false, is_limit && up == 0); // 填 0
            if(!prev && up == 1) ans += f(i - 1, true, is_limit); // 填 1
            if(!is_limit) dp[i][prev] = ans;
            return ans;
        };
        return f(m, false, true); // i 从 m 往小枚举，方便位运算
    }
};